package com.yuxi.al.leercode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 找出最长不重复的子串个数
 * Created by yuxi on 2017/3/28.
 */
public class LongestSubtring {
    public static void main(String[] args) {
        String str = "abcdabdef";
        int index = findLongSubString(str);
        System.out.println(index);

        System.out.println(lengthOfLongestSubstring(str));
    }

    /**
     * 找出最长不重复子串的个数
     * @param s 目标串
     * @return  int  返回个数
     */
    private static int findLongSubString(String s) {
        if (s.length() == 0) return 0;
        //定义一个map。这个map的结构是key为字符，value为对于的坐标
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        //定义一个最大不重复字符的个数
        int max = 0;
        //时间复杂度o(n)
        for (int i = 0, j = 0; i < s.length(); ++i) {
            //hash 里面是否包含，当包含的时候说明需要重新开始找一个子串了，
            // 也就是在这个时候需要重新定义一下j的位置，
            if (map.containsKey(s.charAt(i))) {
                //j 的位置会比i+1大吗 我觉得不可能吧
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            //对于的元素放入map
            map.put(s.charAt(i), i);
            //定位最大子串的位置
            max = Math.max(max, i - j + 1);
        }
        return max;
    }

    /**
     * 利用set处理 最长子字符子串
     * 这个解法的最大好处是简单容易理解，还可以求出最大子串是那些元素
     * 弊端是不能有效的找出子串的顺序
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        //初始化一些变量，定义最大子串的个数
        int i = 0, j = 0, max = 0;
        Set<Character> set = new HashSet<Character>();
        while (j < s.length()) {
            //如果set里面不包含元素，就将这个元素加入到set里面，并且找出最大子串个数
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                max = Math.max(max, set.size());
            } else {
                //如果找到相同的元素，就把他干掉
                set.remove(s.charAt(i++));
            }
        }
        System.out.println(set.toString());
        return max;
    }


}
